from typing import List

"""
有一个一维数组，每个位置的数代表这该位置能向右移动的最大距离；
里面的数取值范围为正负整数和零。
请问能不能从数组开头跳到数组的末尾。
"""


def my_function(nums):
    q = []
    history = []
    n = len(nums) - 1
    for i in range(n):
        if nums[i] >= n - i:
            q.append(i)
            history.append(i)

    while 0 not in q and q != []:
        index = q.pop(0)
        for i in range(n):
            if nums[i] >= index - i and i not in history:
                q.append(i)
                history.append(i)

    if 0 in q:
        return True
    else:
        return False


class Solution:
    def canJump(self, nums: List[int]) -> bool:
        n, rightmost = len(nums), 0
        for i in range(n):
            if i <= rightmost:
                rightmost = max(rightmost, i + nums[i])
                if rightmost >= n - 1:
                    return True
        return False


if __name__ == "__main__":
    nums = [1, 1, 1, 2, 0, 0]
    res = my_function(nums)
    a = Solution()
    print(a.canJump(nums))
